1. Technical Field
This application relates generally to database management.
2. Background of the Related Art
Query optimization is a well-known database management system (DBMS) problem. Given a database query, typically there may be many ways (namely, execution plans) by which the system can produce the query to obtain a result. Although these plans may each produce the same result, one may be more computationally-efficient than another. A query optimizer may be used to examine the various execution plans (in particular, the algebraic expressions) for the query to select the most efficient technique. Once the query optimizer determines the best execution plan, a code generator or interpreter transforms the plan into one or more calls to a query processor, which executes the query.
The execution plan created by the optimizer is expressed as a collection of “operators.” Operators in database systems define the functions that can be executed on one or more streams of incoming rows and emit a single stream of output rows. Operators are a widely accepted way to compose execution plans for queries. Typically, the collection of operators is organized into a tree in which the output from one operator provides the input to the next. To produce the desired result, the operators are applied to the data set, which typically is stored in homogeneous structures (i.e., as a collection of rows all of which are of the same type). A relational query processor in a conventional approach using operators passes streams of homogenous rows from one to another.
U.S. Pat. No. 8,150,850, commonly-owned, describes a database architecture in which data is organized using table groups. A “table group” is a set of tables from a relational database that have a given relationship. In a table group, all the data from at least one row of a “root” table together with all related rows of data from one or more “descendant” tables related thereto are associated together as a composite entity. This association may be physical, in which case the rows are stored in physical proximity to one another in a data store (e.g., in memory, or on disk), or it may be a logical or virtual association. Within the table group, there is one or more root-to-leaf paths (sometimes referred to as “branches”). The patent also described query plan operators (e.g., “horizontal,” or “vertical,” see FIGS. 15A and 16) that are designed to operate on table group-structured data. Those operators, however, operate by examining all the rows in a group; thus, they are not necessarily computationally-efficient.